/*
 * @Author: szx
 * @Date: 2022-02-28 16:21:51
 * @LastEditTime: 2022-02-28 16:45:40
 * @Description:
 * @FilePath: \leetcode\200-299\239\239_2.js
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    const res = [];
    // 单调递减的队列，存放着从大到小的下标值
    const deque = [];
    for (let i = 0; i < nums.length; i++) {
        // 存放从大到小的下标值
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
        deque.push(i);
        // 判断当前最大值（即队首元素）是否在窗口中，若不在便将其出队，这个最大值，只可能是下标最小的那个
        if (deque[0] <= i - k) deque.shift();
        // 当达到窗口大小时便开始向结果中添加数据
        if (i >= k - 1) res.push(nums[deque[0]]);
    }
    return res;
};
console.log(maxSlidingWindow([9, 8, 7, 6, 5, 4, 3, 2, 1], 3));
